home *** CD-ROM | disk | FTP | other *** search
/ The X-Philes (2nd Revision) / The X-Philes Number 1 (1995).iso / xphiles / hp48hor1 / qsdir.doc < prev    next >
Text File  |  1995-03-31  |  10KB  |  229 lines
  1. ****************************************************************************** 
  2. *                 DOCUMENTATION FILE FOR QUICK-SORT ROUTINES                 * 
  3. *                               Version 1.01                                 * 
  4. *                                                                            * 
  5. *                     October 29, 1990  Kevin P. Jessup                      * 
  6. ****************************************************************************** 
  7.  
  8. REVISION HISTORY 
  9. ---------------- 
  10. Version 1.00 of the QSORT routines was a major memory hog.  It was recursive 
  11. and on each pass created a new copy of the list it was trying to sort. 
  12. This required about 15 kbytes of free memory to sort a 100 element list. 
  13. Version 1.01 is still recursive but keeps the list on the stack at all times 
  14. rather than creating a new copy every time the QST subroutine is entered. 
  15. The routines that changed with this upgrade are ASORT, QSORT and QST. 
  16.  
  17. DESCRIPTION 
  18. ----------- 
  19. Hewlett-Packard provides a sorting routine (named SORT) in the programming 
  20. examples section in volume two of the HP48SX owners manual.  Unfortunately, 
  21. it is based on the bubble sort algorithm which is probably the worst sorting 
  22. algorithm available.  This is an implementation of the quick-sort (QSORT) 
  23. algorithm.  QSORT is a general purpose sorting algorithm that is much faster 
  24. than bubble sort in almost all situations. 
  25.  
  26. The chart below compares sort times for the SORT and QSORT routines for lists 
  27. of different size.  The lists contained real integers sorted in reverse order 
  28. upon entry to the routines.  The routines then sorted them into normal 
  29. (ascending) order. 
  30.  
  31.    LIST SIZE       SORT (bubble sort) TIME     QSORT (quick sort) TIME 
  32.    ---------       -----------------------     ----------------------- 
  33.        5                   1.4 seconds                 2.4 seconds 
  34.       10                   5.8                         5.6 
  35.       25                  65.0                        23.1 
  36.       50                 447.0                        81.0 
  37.  
  38. For all but the smallest list sizes, QSORT beats SORT.  For a list of 
  39. 50 elements SORT's execution time was 5 times longer than QSORT. 
  40.  
  41. An assembly language version would be ideal.  This is just "plain" old RPL. 
  42. Perhaps HP already has a quick sort algorithm buried in the 48SX machine code. 
  43. If there is one, the appropriate SYSEVAL addresses may eventually become 
  44. known. 
  45.  
  46. [Note: Jim Donnelly's Tool Library contains LSORT and QSORT commands, written 
  47. in machine language, which are blindingly fast, capable of sorting hundreds of 
  48. items in less than 1 second!  A version of Kevin's program using Donnelly's 
  49. fast sorting can be found on this disk, called "DS".  -jkh-] 
  50.  
  51. Six routines are provided in this package.  Their byte counts, checksums, 
  52. inputs, outputs and descriptions are described below.  Program listings 
  53. conform to an HP48SX translation code setting of 3.  For conveniance, they 
  54. are placed in a directory named QSDIR.  You may want to move all objects 
  55. to your home directory for access by other programs.  The directory checksum 
  56. is # 2A9 (hex).  The directory consumes 829 bytes of memory. 
  57.  
  58. These routines were based on the QSORT routine as described by Kernighan and 
  59. Ritchie in "The C Programming Language", second edition.  Modification was 
  60. necessary to allow recursion on the HP48SX. 
  61.  
  62. ------------------------------------------------------------------------------ 
  63. Name:      QSWAP 
  64. Bytes:     116 
  65. Checksum:  # FBA4 (hex) 
  66. Function:  Subroutine used by QST (described below).  QSWAP will swap 
  67.            two elements in a list. 
  68.  
  69. Listing:   \<< \-> a i j 
  70.            \<< 'a' i GET 'a' j 
  71.            GET 'a' i ROT PUT 
  72.            'a' j ROT PUT a 
  73.            \>> \>> 
  74.  
  75. Input:     Level 3:    list 
  76.            Level 2:    element #1 index 
  77.            Level 1:    element #2 index 
  78.  
  79. Output:    Level 1:    new list 
  80.  
  81. Example:   Level 3:    { 11 12 13 14 15 16 } 
  82.            Level 2:    1 
  83.            Level 1:    6 
  84.            QSWAP 
  85.            Level 1:    { 16 12 13 14 15 11 } 
  86.  
  87. ------------------------------------------------------------------------------ 
  88. Name:      QST 
  89. Bytes:     297.5 
  90. Checksum:  # F84F (hex) 
  91. Function:  The main quick-sort routine. 
  92.  
  93. Listing:   \<< 0 0 \-> l r i last \<< IF l r < THEN l DUP r + 
  94.            2 / QSWAP l 'last' STO l 1 + r FOR i IF DUP i 
  95.            GET OVER l GET 4 PICK EVAL 4 PICK XOR THEN 'last' 
  96.            1 STO+ last i QSWAP END NEXT l last QSWAP l last 1 - 
  97.            QST last 1 + r QST END \>> \>> 
  98.  
  99. Input:     Level 5:    sorting order (0 for normal, 1 for reverse) 
  100.            Level 4:    compare routine 
  101.            Level 3:    list to be sorted 
  102.            Level 2:    left index 
  103.            Level 1:    right index 
  104.  
  105. Output:    Level 3:    sorting order 
  106.            Level 2:    compare routine 
  107.            Level 1:    sorted list 
  108.  
  109. The comparisson routine on level 4 is a function that expects inputs 
  110. on stack levels 1 and 2.  It should compare the 2 objects and return a 
  111. 1 if the object on level 2 is less than the object on level 1.  If 
  112. not, it should return a 0.  See the NSORT and ASORT routines below to 
  113. see how QST is used.  Note that QST is recursive. 
  114.  
  115. ------------------------------------------------------------------------------ 
  116. Name:      QSORT 
  117. Bytes:     51 
  118. Checksum:  # BD12 (hex) 
  119. Function:  Sorts a list of real numbers, strings, etc. 
  120.            Sorts any list of objects that can be compared using the > or 
  121.            < operators. 
  122.  
  123. Listing:   \<< { < } ROT 1 OVER SIZE QST 3 ROLLD DROP2 \>> 
  124.  
  125. Input:     Level 2:    list 
  126.            Level 1:    0 (normal sort) or 1 (reverse sort) 
  127.  
  128. Output:    Level 1:    sorted list 
  129.  
  130. Example 1: Level 2:    { 1 2 3 4 9 8 7 6 5 } 
  131.            Level 1:    1 (reverse sort) 
  132.            QSORT 
  133.            Level 1:    { 9 8 7 6 5 4 3 2 1 } 
  134.  
  135. Example 2: Level 2:    { "ZZZ" "ABC" "abc" "CCB" "CCA" } 
  136.            Level 1:    0 (normal sort) 
  137.            QSORT 
  138.            Level 1:    { "ABC" "CCA" "CCB" "ZZZ" "abc" } 
  139.  
  140. ------------------------------------------------------------------------------ 
  141. Name:      ASORT 
  142. Bytes:     66 
  143. Checksum:  # E13E (hex) 
  144. Function:  Same as QSORT above except all objects in the list are compared 
  145.            as if they were strings (alphabetically). 
  146.  
  147. Listing:   \<< \<< \->STR SWAP \->STR \>= \>> ROT 1 OVER SIZE 
  148.            QST 3 ROLLD DROP2 \>> 
  149.  
  150. Example 1: Level 2:    { 123 1 11 1000 22 } 
  151.            Level 1:    0 
  152.            ASORT 
  153.            Level 1:    { 1 1000 11 123 22 } 
  154.  
  155. Example 2: Level 2:    { QSWAP QST ASORT QSORT NSORT } 
  156.            Level 1:    0 
  157.            ASORT 
  158.            Level 1:    { ASORT DSORT QSORT QST QSWAP } 
  159.  
  160. The above are all the routines necessary for the QSORT package.  A utility 
  161. for sorting HP48SX directories is described below.  It uses the ASORT 
  162. routine just described. 
  163.  
  164. ============================================================================== 
  165. File name: VLPARSE 
  166. Bytes:     184 
  167. Ckecksum:  # 9754 (hex) 
  168. Function:  VLPARSE will take a list of variables and either delete or save 
  169.            all variables of a given type from that list. 
  170.  
  171. Listing:   \<< { } \-> l t d n \<< IF l SIZE DUP THEN 1 SWAP 
  172.            FOR i 'l' i GET IF VTYPE t == d XOR THEN n 'l' 
  173.            i GET 1 \->LIST + 'n' STO END NEXT ELSE DROP END n 
  174.            \>> \>> 
  175.  
  176. Inputs:    Level 3:    LIST of variables 
  177.            Level 2:    object type (see page 97 of manual) 
  178.            Level 1:    0 (to save the variables) or 1 (to delete the variables) 
  179.  
  180. Outputs:   Level 1:    The parsed LIST. 
  181.  
  182. Example 1: 
  183.           1) From your top level directory, execute the VARS command. 
  184.           2) A list of variables should now be on the stack. 
  185.           3) Enter 15 on the stack (this specifies a directory object). 
  186.           4) Enter 0 on the stack (this tell VLPARSE to save all occurences 
  187.               of the object). 
  188.           5) Execute VLPARSE. 
  189.           6) A list of all directory objects remains on the stack. 
  190.          
  191. Example 2: 
  192.           Get a list of all variables in the current directory that do NOT 
  193.           contain PROGRAM objects. 
  194.           1) Execute the VARS command. 
  195.           2) Enter the real number 8 (specifies a program object). 
  196.           3) Enter the real number 1 (delete variables of specified type). 
  197.           4) Execute VLPARSE. 
  198.           5) A list of all variables in the current directory that are NOT 
  199.              program objects remains on the STACK.  If all objects in the 
  200.              current directory WERE program objects, the list is empty. 
  201.  
  202. ------------------------------------------------------------------------------ 
  203. File name: DSORT (Directory SORT) 
  204. Bytes:     98.5 
  205. Ckecksum:  # E97B (hex) 
  206. Function:  DSORT will sort a directory alphabeticly.  Sub-directores will 
  207.            be sorted first, followed by all other objects.  Note that 
  208.            DSORT calls VLPARSE and ASORT as subroutines. 
  209.  
  210. Listing:   \<< VARS 15 0 VLPARSE 0 ASORT 
  211.                VARS 15 1 VLPARSE 0 ASORT 
  212.                + ORDER \>> 
  213.  
  214. Inputs:    None 
  215.  
  216. Outputs:   The current directory is sorted.  The actual variables within the 
  217.            subdirectories are NOT sorted. 
  218.  
  219. *************************************************************************** 
  220.  
  221. Support the HP48SX BBS shareware concept by sending a couple-a-bucks to the 
  222. author OR posting your own USEFULL programs to the HP48SX BBS. 
  223.  
  224. Kevin Jessup 
  225. 9118 N. 85th St. 
  226. Milwaukee, WI 53224 
  227.  
  228. ***********************************[END]*********************************** 
  229.